package com.example.leetcode.DFS;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 题目描述
 * 给定一个二维的 0-1 矩阵，其中 0 表示海洋，1 表示陆地。单独的或相邻的陆地可以形成岛
 * 屿，每个格子只与其上下左右四个格子相邻。求最大的岛屿面积。
 *
 * 输入输出样例
 * 输入是一个二维数组，输出是一个整数，表示最大的岛屿面积。
 *
 * Input:
 * [[1,0,1,1,0,1,0,1],
 * [1,0,1,1,0,1,1,1],
 * [0,0,0,0,0,0,0,1]]
 * Output: 6
 * 最大的岛屿面积为 6，位于最右侧。
 *
 * @ClassName Soluction_695
 * @Description TODO
 * @Author liuzhihui
 * @Date 2/5/2021 下午 10:29
 * @Version 1.0
 **/
public class Soluction_1_695 {
    public static void main(String[] args) {

    }
    //方式一：递归方式，沉岛思想
    // 遍历所有元素，如果当前元素是1，从四个方向找是否还有是1的元素，有，加继续加
    public static int maxAreaOfIsland(int[][] grid) {
        int res = 0;

        //遍历所有元素
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // 如果当前元素是1，从各个方向找元素，并加起来
                if (grid[i][j] ==1){
                    res = Math.max(res,getMaxArea(i, j, grid));
                }
            }
        }
        return res;
    }
    private static int getMaxArea(int i, int j, int[][] grid) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0){
            return 0;
        }
        // 把找到的岛屿改成0,沉岛，避免重复加岛屿面积
        grid[i][j] =0;
        // 岛屿面积加1
        int num = 1;

        //向右找是否还有是1的
        num = num + getMaxArea(i, j + 1,grid);
        //向左找
        num = num + getMaxArea(i, j - 1,grid);
        // 向上找
        num = num + getMaxArea(i - 1, j,grid);
        // 向下找
        num = num + getMaxArea(i + 1, j,grid);
        return num;
    }

    //方式二：深度优先遍历DFS,栈实现
    // 思路：定义一个栈，用来存储当前元素的索引，遍历二维数组，将当前元素的索引放到
    // 栈中，遍历栈，从栈中获取元素，判断获取到的索引对应的元素是否是1，是的话，计算
    // 面积，沉岛，同时将其他方向的元素，压栈
    public  static int maxAreaOfIsland1(int[][] grid){
        //定义栈,存储元素的下标
        Deque<int[]> deque = new LinkedList<>();
        // 定义岛屿的四周
        int[][] moveIndex =new int[][]{{-1,0}, {1,0}, {0,1 }, {0, -1}};
        int maxArea = 0;

        //遍历数组
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                //将当前元素的下标压栈
                deque.push(new int[]{i,j});
                //计算最大面积
                int currMaxArea = 0;

                //遍历栈
                while(!deque.isEmpty()){
                    //从栈中获取元素的下标
                    int[] poll = deque.pop();
                    int x = poll[0];
                    int y = poll[1];
                    // 过滤元素
                    if ( x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0){
                        continue;
                    }
                    // 找到岛屿，沉岛
                    grid[x][y] = 0;
                    // 面积加一
                    currMaxArea+=1;
                    //往当前岛屿的四周找找，说不定还有岛屿
                    for (int i1 = 0; i1 < moveIndex.length; i1++) {
                        deque.push(new int[]{x + moveIndex[i1][0], y + moveIndex[i1][1]});
                    }
                }
                maxArea = Math.max(currMaxArea, maxArea);
            }

        }
        return maxArea;
    }

    // 栈实现，第一次练习
    public static int maxAreaOfIsland2(int[][] grid){
        Deque<int[]> stack= new LinkedList<>();
        int[][] moveIndex = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        int maxArea = 0;

        //遍历数组
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                stack.add(new int[]{i, j});
                int curArea = 0;

                while(!stack.isEmpty()){
                    int[] pop = stack.pop();
                    int x = pop[0];
                    int y = pop[1];

                    if(x < 0 || x >= grid.length || y < 0 || y >= grid[0].length || grid[x][y] == 0){
                        continue;
                    }

                    grid[x][y] = 0;
                    curArea++;

                    for (int[] index : moveIndex) {
                        stack.add(new int[]{x + index[0], y + index[1]});
                    }
                }
                maxArea = Math.max(maxArea,curArea);
            }
        }

        return maxArea;
    }

    //递归方式，第一次练习
    public int maxAreaOfIsland3(int[][] grid){
        int maxArea = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1){
                    maxArea = Math.max(maxArea,getMaxArea1(i, j ,grid));
                }
            }
        }
        return maxArea;
    }
    private int getMaxArea1(int i, int j, int[][] grid) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0){
            return 0;
        }
        grid[i][j] = 0;
        int curArea = 1;
        curArea += getMaxArea1(i-1, j, grid);
        curArea += getMaxArea1(i+1, j, grid);
        curArea += getMaxArea1(i, j - 1, grid);
        curArea += getMaxArea1(i, j + 1, grid);
        return curArea;
    }

    // 递归方式，第二次练习
    public static int maxAreaOfIsland4(int[][] grid){
        int result = 0;

        // 遍历所有元素
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // 判断当前元素是否1
                if(grid[i][j] == 1){
                    // 寻找其他方向是否还有岛屿
                    result =Math.max(result,getMaxArea4(i, j, grid));
                }
            }
        }
        return result;
    }
    private static int getMaxArea4(int i, int j, int[][] grid) {
        // 这些坐标要在二维数组上并且是岛屿
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == 0){
            return 0;
        }
        // 把当前岛屿沉了
        grid[i][j] = 0;
        // 设置岛屿面积
        int num = 1;

        // 向左边找岛屿
        num += getMaxArea4(i, j - 1, grid);
        // 向右边找岛屿
        num += getMaxArea4(i, j + 1, grid);
        // 向上边找岛屿
        num += getMaxArea4(i - 1, j, grid);
        // 向下边找岛屿
        num += getMaxArea4(i + 1, j, grid);

        return num;
    }
    // 栈实现，第二次练习
    public static int maxAreaOfIsland5(int[][] grid){
        int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        Deque<int[]> deque = new LinkedList<>();
        int maxArea = 0;

        // 遍历二维数组
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                // 将当前元素的索引压栈
                deque.add(new int[]{i, j});
                int num = 0;

                // 遍历栈
                while(!deque.isEmpty()){
                    int[] pop = deque.pop();
                    int x = pop[0];
                    int y = pop[1];
                    if (x < 0 || y < 0 || x >= grid.length || y>= grid[0].length || grid[x][y] == 0){
                        continue;
                    }
                    // 沉岛
                    grid[x][y] = 0;
                    num++;

                    for (int z = 0; z < 4; z++) {
                        deque.add(new int[]{x + directions[z][0], y + directions[z][1]});
                    }
                }
                maxArea = Math.max(maxArea, num);
            }
        }
        return maxArea;
    }

    // -----------------------------------------------------------------------------------------------------------------
    // 第三次练习，深度优先搜索
    // 沉岛思维和使用布尔数组来，标记是否访问过
    public static int maxAreaOfIsland6(int[][] grid){
        int result = 0;
        boolean[][] visited =new boolean[grid.length][grid[0].length];

        //遍历二维数组
        for (int i = 0; i < grid.length; i++) {
            for (int i1 = 0; i1 < grid[0].length; i1++) {
                if (grid[i][i1] == 1){
                    result = Math.max(result,dfs(grid, i , i1,visited));
                }
            }
        }
        return result;
    }

    private static int dfs(int[][] grid, int i, int j,boolean[][] visited) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != 1 || visited[i][j]){
            return 0;
        }
        // 沉岛
//        grid[i][j] = 0;
        visited[i][j] = true;
        int num = 1;

        //向右找是否还有是1的
        num = num + dfs(grid, i - 1 ,j,visited);
        //向左找
        num = num + dfs(grid, i + 1,j,visited);
        // 向上找
        num = num + dfs(grid, i, j + 1,visited);
        // 向下找
        num = num + dfs(grid, i, j - 1,visited);
        return num;
    }

}
